package _06_动态规划;

/**
 * https://leetcode-cn.com/problems/unique-paths-ii/
 *
 * @Author: haogege
 * @Date: 2021/9/12
 */
public class _63_不同路径_II {

    public static void main(String[] args) {

        int[][] ints = {
                {0, 0, 0}, {0, 1, 0}, {0, 0, 0}
        };

        _63_不同路径_II ii = new _63_不同路径_II();
        System.out.println(ii.uniquePathsWithObstacles(ints));

    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 定义dp数组
        int rows = obstacleGrid.length;
        int cols = obstacleGrid[0].length;
        int[][] dp = new int[rows][cols];
        // 初始化dp数组
        for (int row = 0; row < rows; row++) {
            if (obstacleGrid[row][0] == 1) {
                break;
            }
            dp[row][0] = 1;
        }
        for (int col = 0; col < cols; col++) {
            if (obstacleGrid[0][col] == 1) {
                break;
            }
            dp[0][col] = 1;
        }

        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                // 查看当前位置是否右障碍物
                if (obstacleGrid[row][col] == 1) {
                    continue;
                }
                // 当前路径条数，等于左上路径相加
                dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
            }
        }
        return dp[rows - 1][cols - 1];
    }

}
